Метод БВЕ
Метод БВЕ (быстрого вычисления E-функций) — метод быстрого суммирования специального вида рядов. Построен в 1990 году Е. А. Карацубой[1][2]. Позволяет вычислять быстро зигелевские E-функции, и в частности, [math]\displaystyle{ e^x }[/math].
Зигель назвал «E-функциями» класс функций, «похожих на экспоненциальные». Этому классу принадлежат такие высшие трансцендентные функции как гипергеометрические, сферические, цилиндрические функции и так далее.
Теорема
С помощью БВЕ можно доказать следующую теорему
- Теорема.
Пусть [math]\displaystyle{ y=f(x) }[/math] — простейшая трансцендентная функция, то есть экспоненциальная функция или тригонометрическая функция, или элементарная алгебраическая функция, или их суперпозиция, или обратная им функция или суперпозиция обратных функций. Тогда
[math]\displaystyle{ s_f(n) = O(M(n)\log^2n). }[/math]
Здесь [math]\displaystyle{ s_f(n) }[/math] есть сложность вычисления (битовая) функции [math]\displaystyle{ f(x) }[/math] с точностью до [math]\displaystyle{ n }[/math] знаков, [math]\displaystyle{ M(n) }[/math] — сложность умножения двух [math]\displaystyle{ n }[/math]-значных чисел.
Алгоритмы, основанные на БВЕ, включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант [math]\displaystyle{ e }[/math], [math]\displaystyle{ \pi }[/math], постоянной Эйлера [math]\displaystyle{ \gamma }[/math], постоянных Апери[3] и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций[4], сферических функций, цилиндрических функций[5] и так далее для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента[6][7], дзета-функции Гурвица для целого аргумента и алгебраических значений параметра[8], а также таких специальных интегралов[9], как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и так далее при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно [math]\displaystyle{ s_{f}(n)=O(M(n)\log^2 n). }[/math]
В настоящее время только метод БВЕ даёт возможность быстро вычислять значения функций из класса высших трансцендентных функций[10], некоторые специальные интегралы математической физики и такие классические константы, как константы Эйлера, Каталана[11] и Апери. Дополнительным преимуществом метода БВЕ является возможность распараллеливания основанных на БВЕ алгоритмов.
БВЕ-вычисление классических констант
Для быстрого вычисления константы [math]\displaystyle{ \pi }[/math] можно воспользоваться формулой Эйлера [math]\displaystyle{ \frac{\pi}{4} = \mathrm{arctg}\frac12 + \mathrm{arctg}\frac13, }[/math] и применить БВЕ к суммированию рядов Тейлора для
[math]\displaystyle{ \mathrm{arctg}\frac12 = \frac{1}{1\cdot 2} - \frac{1}{3\cdot 2^3}+ \ldots + \frac{(-1)^{r-1}}{(2r-1)2^{2r-1}} + R_1, }[/math]
[math]\displaystyle{ \mathrm{arctg}\frac13 = \frac{1}{1\cdot 3} - \frac{1}{3\cdot 3^3}+ \ldots + \frac{(-1)^{r-1}}{(2r-1)3^{2r-1}} + R_2, }[/math]
с остаточными членами [math]\displaystyle{ R_1,\ R_2, }[/math] для которых справедливы оценки
[math]\displaystyle{ |R_1| \leqslant \frac45\frac{1}{2r+1}\frac{1}{2^{2r+1}}; }[/math]
[math]\displaystyle{ |R_2| \leqslant \frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}}; }[/math]
и при
[math]\displaystyle{ r = n, }[/math]
[math]\displaystyle{ 4(|R_1|+|R_2|) \ \lt \ 2^{-n}. }[/math]
Чтобы вычислить [math]\displaystyle{ \pi }[/math] посредством БВЕ, можно использовать также другие приближения[12]. Во всех случаях сложность
[math]\displaystyle{ s_{\pi} = O(M(n)\log^2 n). }[/math]
Чтобы вычислить постоянную Эйлера [math]\displaystyle{ \gamma }[/math] с точностью до [math]\displaystyle{ n }[/math] знаков, нужно просуммировать с помощью БВЕ два ряда. А именно, при [math]\displaystyle{ m=6n,\ k = n,\ k \geqslant 1, }[/math]
[math]\displaystyle{ \gamma = -\log n \sum_{r=0}^{12n}\frac{(-1)^rn^{r+1}}{(r+1)!} +\sum_{r=0}^{12n}\frac{(-1)^rn^{r+1}}{(r+1)!(r+1)} +O(2^{-n}). }[/math]
При этом
[math]\displaystyle{ s_{\gamma} = O(M(n)\log^2 n). }[/math]
Для быстрого вычисления константы [math]\displaystyle{ \gamma }[/math] можно также применить метод БВЕ к другому приближению[13]
БВЕ-вычисление некоторых степенных рядов
С помощью БВЕ можно вычислить быстро следующие два вида рядов:
[math]\displaystyle{ f_1 = f_1(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}z^j, }[/math]
[math]\displaystyle{ f_2 = f_2(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}\frac{z^j}{j!}, }[/math]
при условии, что [math]\displaystyle{ a(j),\ b(j) }[/math] — целые числа, [math]\displaystyle{ |a(j)|+|b(j)| \leqslant (Cj)^K;\ |z| \lt 1;\ K }[/math] и [math]\displaystyle{ C }[/math] есть константы, и [math]\displaystyle{ z }[/math] есть алгебраическое число.
Сложность вычисления этих рядов
[math]\displaystyle{ s_{f_1}(n)=O\left(M(n)\log^2n \right), }[/math]
[math]\displaystyle{ s_{f_2}(n)=O\left(M(n)\log n \right). }[/math]
Детали БВЕ на примере быстрого вычисления константы [math]\displaystyle{ e }[/math]
Для вычисления константы [math]\displaystyle{ e }[/math] возьмём [math]\displaystyle{ m = 2^k,\quad k \geqslant 1 }[/math], членов ряда Тейлора для [math]\displaystyle{ e, }[/math]
[math]\displaystyle{ e = 1 + \frac{1}{1!} + \frac{1}{2!} + \ldots + \frac{1}{(m-1)!} + R_m. }[/math]
При этом выбираем [math]\displaystyle{ m }[/math] так, чтобы для остатка [math]\displaystyle{ R_m }[/math] выполнялось неравенство [math]\displaystyle{ R_m \leqslant 2^{-n-1} }[/math]. Это будет, например, когда [math]\displaystyle{ m\geqslant \frac{4n}{\log n} }[/math]. Таким образом, возьмем [math]\displaystyle{ m=2^k }[/math] таким, что натуральное число [math]\displaystyle{ k }[/math] определяется неравенствами:
[math]\displaystyle{ 2^k \geqslant \frac{4n}{\log n} \gt 2^{k-1}. }[/math]
Будем вычислять сумму [math]\displaystyle{ S = 1 + \frac{1}{1!} + \frac{1}{2!} + \ldots + \frac{1}{(m-1)!} = \sum_{j=0}^{m-1}\frac{1}{(m-1-j)!}, }[/math]
за [math]\displaystyle{ k }[/math] шагов следующего процесса.
Шаг 1. Объединяя слагаемые [math]\displaystyle{ S }[/math] последовательно попарно и вынося за скобки «очевидный» общий множитель, получаем
[math]\displaystyle{ S = \left(\frac{1}{(m-1)!} + \frac{1}{(m-2)!}\right) + \left(\frac{1}{(m-3)!} + \frac{1}{(m-4)!}\right) + \ldots = }[/math]
[math]\displaystyle{ = \frac{1}{(m-1)!}(1+m-1) + \frac{1}{(m-3)!}(1+m-3) + \ldots }[/math]
Будем вычислять только целые значения выражений, стоящих в скобках, то есть значения [math]\displaystyle{ m,\ m-2,\ m-4,\ \ldots }[/math]
Таким образом, на первом шаге сумма [math]\displaystyle{ S }[/math] преобразуется к виду
[math]\displaystyle{ S = S(1) = \sum_{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}\alpha_{m_1-j}(1), }[/math]
[math]\displaystyle{ m_1 = \frac m2,\ m = 2^k,\ k \geqslant 1. }[/math]
На первом шаге вычисляется только [math]\displaystyle{ \frac m2 }[/math] целых чисел вида
[math]\displaystyle{ \alpha_{m_1-j}(1) = m-2j,\quad j = 0,\;1,\;\ldots,\;m_1 - 1, }[/math]
Далее мы действуем аналогично: объединяя на каждом шаге слагаемые суммы [math]\displaystyle{ S }[/math] последовательно попарно, мы выносим за скобки «очевидный» общий множитель и вычисляем только целые значения выражений в скобках. Пусть сделано [math]\displaystyle{ i }[/math] шагов такого процесса.
Шаг [math]\displaystyle{ i+1 }[/math] ([math]\displaystyle{ i+1 \leqslant k }[/math]).
[math]\displaystyle{ S = S(i+1) = \sum_{j=0}^{m_{i+1}-1}\frac{1}{(m-1-2^{i+1}j)!}\alpha_{m_{i+1}-j}(i+1), }[/math]
[math]\displaystyle{ m_{i+1} = \frac{m_i}{2} = \frac{m}{2^{i+1}}, }[/math]
мы вычисляем только [math]\displaystyle{ \frac{m}{2^{i+1}} }[/math] целых чисел вида
[math]\displaystyle{ \alpha_{m_{i+1}-j}(i+1) = \alpha_{m_i-2j}(i) + \alpha_{m_i-(2j+1)}(i)\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!}, }[/math]
[math]\displaystyle{ j = 0,\;1,\;\ldots,\quad m_{i+1} - 1,\quad m = 2^k,\quad k \geqslant i+1. }[/math]
Здесь [math]\displaystyle{ \frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!} }[/math] есть произведение [math]\displaystyle{ 2^i }[/math] целых чисел.
И так далее.
Последний, [math]\displaystyle{ k }[/math]-й шаг. Вычисляем одно целое значение [math]\displaystyle{ \alpha_1(k) }[/math], вычисляем, пользуясь вышеописанным быстрым алгоритмом, значение [math]\displaystyle{ (m-1)! }[/math], и производим одно деление целого числа [math]\displaystyle{ \alpha_1(k) }[/math] на число [math]\displaystyle{ (m-1)! }[/math] с точностью до [math]\displaystyle{ n }[/math] знаков. Получившийся результат и есть сумма [math]\displaystyle{ S }[/math], или константа [math]\displaystyle{ e }[/math] с точностью до [math]\displaystyle{ 2^{-n} }[/math]. Сложность всех вычислений есть
[math]\displaystyle{ O\left(M(m)\log^2 m\right) = O\left(M(n)\log n\right). }[/math]
Примечания
- ↑ Карацуба Е. А. Быстрое вычисление трансцендентных функций. Проблемы передачи информации, т. 27, № 4 (1991).
- ↑ Lozier D. W. and Olver F. W. J. Numerical Evaluation of Special Functions. Mathematics of Computation 1943—1993: A Half-Century of Computational Mathematics, W. Gautschi, eds., Proc. Sympos. Applied Mathematics, AMS, Vol. 48 (1994).
- ↑ Карацуба Е. А. Быстрое вычисление [math]\displaystyle{ \zeta(3) }[/math]. Проблемы передачи информации, т. 29, № 1 (1993).
- ↑ Karatsuba Ekatharine A. Fast evaluation of hypergeometric function by FEE. Computational Methods and Function Theory (CMFT’97), N. Papamichael, St. Ruscheweyh and E. B. Saff, eds., World Sc. Pub. (1999).
- ↑ Karatsuba Catherine A. Fast evaluation of Bessel functions. Integral Transforms and Special Functions, Vol. 1, № 4 (1993).
- ↑ Карацуба Е. А. Быстрое вычисление дзета-функции Римана [math]\displaystyle{ \zeta(s) }[/math] для целых значений аргумента [math]\displaystyle{ s }[/math]. Проблемы передачи информации, т. 31, № 4 (1995).
- ↑ Borwein J. M., Bradley D. M. and Crandall R. E. Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math., Vol. 121, № 1-2 (2000).
- ↑ Карацуба Е. А. Быстрое вычисление дзета-функции Гурвица и [math]\displaystyle{ L }[/math]-рядов Дирихле. Проблемы передачи информации, т. 34, № 4 (1998).
- ↑ Karatsuba E. A. Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W. Kramer, J. W. von Gudenberg, eds. (2001).
- ↑ Bach E. The complexity of number-theoretic constants. Info. Proc. Letters, № 62 (1997).
- ↑ Karatsuba E. A. Fast computation of [math]\displaystyle{ \zeta(3) }[/math] and of some special integrals, using the polylogarithms, the Ramanujan formula and it’s generalization. J. of Numerical Mathematics BIT, Vol. 41, № 4 (2001).
- ↑ Bailey D. H., Borwein P. B. and Plouffe S. On the rapid computation of various polylogarithmic constants. Math. Comp., Vol. 66 (1997).
- ↑ Brent R. P. and McMillan E. M. Some new algorithms for high-precision computation of Euler’s constant. Math. Comp., Vol. 34 (1980).
Ссылки
Для улучшения этой статьи желательно: |